For years, the bar code has been promoted as a machine-readable symbology. A bar code is a one-dimensional symbol that contains a unique serial number encoded in black and white bars. Bar codes are widely used as indices to associate physical objects with larger databases containing more detailed information. Thus, the bar code itself often provides no useful information beyond, for example, a zip code.
As the demand for information-based technologies grows, there is considerable interest in eliminating the associated database and storing more data information in the symbology itself. With current technology, encoding additional information makes a one-dimensional bar code unrealistically long. A number of two-dimensional symbologies, either in the form of a stacked bar code or a matrix type, have been introduced to accommodate this need. One of them, the MaxiCode symbology, is described in U.S. Pat. Nos. 4,874,936 and 4,896,029.
Two-dimensional symbologies such as the MaxiCode cannot be acquired and decoded by the laser spot scanners typically used to scan single line bar codes. Attempts have been made to modify such devices to perform raster scanning operations on stacked bar codes and two-dimensional codes. However, this approach is too lengthy for practical high speed applications. A faster method is to acquire an image of the entire two-dimensional symbology using an electronic camera. Charge-coupled device (CCD) sensor arrays of the type used in video cameras are suitable. They consist of a matrix of "pixels" each of which stores a cumulative charge according to the amount of light which strikes the pixel. The pixel values are read out, converted and stored in a corresponding matrix in a digital memory for evaluation and processing.
An important use for optically encoded, machine-readable symbologies has been on labels attached to packages, letters, baggage, containers and the like. While in the case of bar codes, the information carried on the label may be only a key to a remote database, or possibly a zip code, two-dimensional symbologies are database independent and can carry information pertaining to full destination address, origin, nature of the contents, routing, sorting, tracking, and the like. The symbology reader must be able to evaluate an image taken within a wide range of orientations relative to the reader camera, because it is difficult and impractical to precisely align the symbology with the CCD detector. Typically, therefore, the rows of optical elements of the symbology will not be aligned in the image with the rows of pixels forming the CCD.
As a result, the reader must be able to recognize the presence of a symbology, determine its location in the image, and determine its orientation before attempting to decode the encoded information. Acquisition targets have been long used for automatic aiming in the area of computer and robotic vision systems. There are many forms of acquisition targets such as round circle, cross sign and bar. An example of a label acquisition symbol is described in U.S. Pat. No. 4,776,464. The type of target consisting of concentric rings is the most preferable because of its unique feature of being omnidirectionally symmetric along the center. Placing such a target on objects being searched makes it possible to locate the objects in real time by a sensing mechanism.
As disclosed in U.S. Pat. Nos. 4,874,936 and 4,896,029, the MaxiCode symbology contains a set of concentric rings or bull's-eye at the center of the symbology. This acquisition target of alternating levels of black and white is embedded to facilitate an imaging and decoding device to locate the label instantly in an unconstructed environment. The advantage of using such an acquisition target becomes apparent when labels to be located are affixed on the surface of objects on a fast moving conveyer belt, and must be read and decoded by an overhead decoding system for routing and sorting purposes.
U.S. Pat. Nos. 4,874,936 and 4,896,029 disclose analog and digital methods for locating the bull's-eye acquisition target. All known methods converge to one principle, namely having a template for comparison measurement. As described fully in the '936 and '029 patents, a template of the ring structure is used to move around the image data comprising the acquisition target 100. The matching or locating process is done when the data difference between the template and the image data underlying the template reaches a minimum error. As the size of the acquisition target 100 or image resolution changes, with a fixed template, it is unlikely that the location with the minimum error still indicates the presence of the acquisition target 100. Furthermore, there may be many locations with similar minimum errors indicating many false targets. Similar erroneous results may be obtained when the imaged acquisition target possesses tilt angle distortion.
Furthermore, it has been shown that tremendous computational power is required for direct implementation. Different computational methods have been proposed to reduce the computational complexity. For example, a run length coding technique may be applied to transfer the original grey label image into a coded image through a thresholding process. The image is then compared with a similarly encoded template pattern. While the improved method is able to reduce the computational time significantly, it fails to find the target when a label image is modestly distorted or its resolution varies slightly. Also, the incorrect choice of threshold value for color transitions in the image may alter the width of rings of the acquisition target, so that the comparison measurement can not be reliably performed.
To account for variations in the size of the image due to variations in the distance from the object to the CCD detector, and distortion caused by the imaging angle, multiple patterns of different sizes or distortion factors may have to be stored as different templates. Since the size of a label image is not predefined, each template has to be tried successively in order to locate the target. This is impractical in reality due to the processing time involved.
Thus, this method of bull's-eye detection using matching comparisons, has several disadvantages. A match to the template may be produced by a coincidental arrangement of data cells within the symbology, and therefore may not necessarily indicate the location of the bull's-eye. Further, any change in the size of the image affects the measured frequency. The image size may vary not only as a result of printing different sizes, but also as a result of varying distances between the symbology and the camera. For example, it is difficult to require that a (noncontact) hand held reader be held at the same fixed distance to all the packages. As noted, multiple templates must be compared to the image to account for size variations, adding complexity and time to the procedure, and increasing the possibility of a false "find." Problems in matching the template frequency can also arise from tilting the camera and label relative to one another, which results in a distorted image. This distortion changes the frequency of the stored image, as compared to that of an undistorted template.
Finally, the accuracy of matching the frequency increases with the number of concentric rings, but this may increase the area of the symbology devoted to the bull's-eye and decrease the area available to carry information.
There is a great need for a new system which is able to overcome the described problems. There has further been a need in the art for a system of reduced computational complexity for locating two-dimensional acquisition targets, which at the same time is more efficient and more reliable. There also has been a need for such a system that can efficiently locate an acquisition target regardless of its size.